import heapq
from collections import defaultdict


class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]


# dict

def tree(): return defaultdict(tree)

def destruct(d, items):
    """
    Destruct a dictionary in Clojure ways, will raise an exception
    when key not exists.
    """
    return [d[it] for it in items]


# binary

def hexdump(bts, rowlen=16):
    """
    Dump the bytes to a readable hex table
        :param bts <bytes>
        :param rowlen <int> :the length of a row
        :return HexTable <str>
    """
    table = []
    for i in range(0, len(bts), rowlen):
        s = bts[i:i + rowlen]
        hexn = ' '.join([ '%02X' % x for x in s ])
        text = ''.join([ chr(x) if 0x20 <= x < 0x7f else '.' for x in s ])
        table.append('| %04X | %-*s | %-*s |'
                     % (i, rowlen * 3 - 1, hexn, rowlen, text))
    return '\n'.join(table)


def passwd(pswd, sha, salt=None, rounds=12):
    if not salt or len(salt) != 32:
        salt = os.urandom(32)
    storage = pswd if isinstance(pswd, bytes) else pswd.encode()
    for i in range(rounds):
        storage = sha(salt[:2 * i] + storage + salt[2 * i:])
    return salt, storage


# string and list (iterable)

def allof(test, sequence):
    return all(map(test, sequence))

def anyof(test, sequence):
    return any(map(test, sequence))

def areinstances(sequence, types):
    return allof(lambda x: isinstance(x, types), sequence)

def spread(iterable):
    return [ x for x in iterable ]

def editdist(s1, s2):
    """
    Calculate the 'local edit distance' of the two strings
        :param s1, s2 <str>
        :return similarity <float>
    """
    if not s1 or not s2: return 0
    l1, l2 = map(len, (s1, s2))
    distance = 0
    matrix = [ [0] * (l2+1) for i in range(l1+1) ]
    _equal = lambda a, b: +1 if a == b else -1
    for i in range(1, l1 + 1):
        for j in range(1, l2 + 1):
            matrix[i][j] = max(0, matrix[i-1][j] - 1, matrix[i][j-1] - 1,
                               matrix[i-1][j-1] + _equal(s1[i-1], s2[j-1]))
            distance = max(distance, matrix[i][j])
    return distance / min(len(s1), len(s2))

def hamdist(s1, s2):
    """
    Calculate the 'Hamming distance' of the two strings
        :param s1, s2 <str>
        :return similarity <float>
    """
    assert len(s1) == len(s2)
    return sum(map(operator.ne, s1, s2)) # / len(s1)

# vector

def sim_distance(v1, v2):
    """
    Euclidean distance score
    """
    return 1 / (1 + sum((v1 - v2) ** 2))

def sim_pearson(v1, v2):
    """
    Pearson correlation score
    """
    pass

def divide(lst, length):
    """Divide `lst` by `length`"""
    return [ x for x in zip(*[ iter(lst) ] * length) ]
